//
//  SNSortClass.m
//  project
//
//  Created by 黄建华 on 2018/5/9.
//  Copyright © 2018年 黄建华. All rights reserved.
//

#import "SNSortClass.h"

@implementation SNSortClass

+ (NSArray *)sortByMaoPao:(NSArray *)array {
    NSMutableArray *numbers = [NSMutableArray arrayWithArray:array];
    
    for (int i = 0; i < array.count; i++) {
        //比较的躺数
        for (int j = 0; j < array.count - 1; j++) {
            //比较的次数
            if ([numbers[j] intValue] > [numbers[j + 1] intValue]) {
                //这里为升序排序
                int temp = [numbers[j] intValue];
                numbers[j] = numbers[j + 1];
                //OC中的数组只能存储对象，所以这里转换成string对象
                numbers[j + 1] = [NSString stringWithFormat:@"%d", temp];
            }
        }
    }
    return numbers;
}

+ (NSArray *)sortByChoose:(NSArray *)array {
    NSMutableArray *numbers = [NSMutableArray arrayWithArray:array];
    //选择
    for (int i = 0; i < [numbers count]-1; i++) {
        for (int j = i+1; j < [numbers count]; j++) {
            if ([numbers[i] intValue] > [numbers[j] intValue]) {
                //交换
                [numbers exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }
    return numbers;
}

+ (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
    if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
        return ;
    }
    
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    //记录比较基准数
    NSInteger key = [array[i] integerValue];
    
    while (i < j) {
        /**** 首先从右边j开始查找比基准数小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
            j--;
        }
        //如果比基准数小，则将查找到的小值调换到i的位置
        array[i] = array[j];
        
        /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
            i++;
        }
        //如果比基准数大，则将查找到的大值调换到j的位置
        array[j] = array[i];
        
    }
    
    //将基准数放到正确位置
    array[i] = @(key);
    
    /**** 递归排序 ***/
    //排序基准数左边的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基准数右边的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
    if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
        return ;
    }
    
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    //记录比较基准数
    NSInteger key = [array[i] integerValue];
    
    while (i < j) {
        /**** 首先从右边j开始查找比基准数小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
            j--;
        }
        //如果比基准数小，则将查找到的小值调换到i的位置
        array[i] = array[j];
        
        /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
            i++;
        }
        //如果比基准数大，则将查找到的大值调换到j的位置
        array[j] = array[i];
        
    }
    
    //将基准数放到正确位置
    array[i] = @(key);
    
    /**** 递归排序 ***/
    //排序基准数左边的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基准数右边的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

@end

